#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include "tiempo.h"

using namespace std;

typedef struct {
	int inicio;
	int fin;
} Curso;

void leerStdin();
void elegir_cursos(int cantCursos, vector<Curso> cursos, int iter);
bool snd_order(Curso, Curso);
void imprimir_tiempos_ejecucion(unsigned long long int cant_ciclos, int cant_elem, const char* archivoOut);

int main(int argc, char *argv[]) {
	leerStdin();
	printf("Fin de tests\n");
	return 0;
}

void leerStdin() {
	int cantIter;
	cin >> cantIter;

	while(1){
		/* Leer instancia */
		int cantCursos(0);

		Curso curso;
		vector<Curso> cursos(cantCursos);
		if(!(cin >> cantCursos)) break;

		for(int i = 0; i < cantCursos; i++) {
			cin >> curso.inicio;
			cin >> curso.fin;
			cursos.push_back(curso);
		}				
		elegir_cursos(cantCursos, cursos, cantIter);
	}
}

void elegir_cursos(int cantCursos, vector<Curso> cursos, int iter) {
	unsigned long long int start, end, res;
	vector<Curso> temp = cursos;
	res = 0;
	const char* archivoOut = "res_performance.txt";

	for (int j=0; j < iter; j++) {
		MEDIR_TIEMPO_START(start);

		cursos = temp;
		int ultima_fecha = 0;
		vector<Curso> resultado;
		
		make_heap(cursos.begin(), cursos.end(), snd_order);
		// sort_heap(cursos.begin(), cursos.end(), snd_order);

		for(int i = 0; i < cantCursos; i++) {
			if(cursos.front().inicio <= ultima_fecha){
				pop_heap(cursos.begin(), cursos.end(), snd_order); //Mandamos el primer elemento al final de la lista
				cursos.pop_back(); //eliminamos el último elemento
			} else {
				ultima_fecha = cursos.front().fin;
				resultado.push_back(cursos.front());
				pop_heap(cursos.begin(), cursos.end(), snd_order); //Mandamos el primer elemento al final de la lista
				cursos.pop_back(); //eliminamos el último elemento
			}
		}

		MEDIR_TIEMPO_STOP(end);
		res = res + (end-start);
	}

	res = res / iter;
	imprimir_tiempos_ejecucion(res, cantCursos, archivoOut);
}

bool snd_order(Curso c1, Curso c2) {
	return (c1.fin > c2.fin); // originalmente estaba c1.fin < c2.fin ... pero me parece que va mayor en realidad
}

void imprimir_tiempos_ejecucion(unsigned long long int cant_ciclos, int cant_elem, const char* archivoOut) {
	FILE* archivo = fopen(archivoOut, "a" );
	
	fprintf(archivo, "%i\t", cant_elem);
	fprintf(archivo, "%i\n", (unsigned int)cant_ciclos);	
	 
	fclose(archivo);
}